package com.test.daily.leetcode.y2022.m07.day0701.day0703.v01;

/**
 * @author Tom on 2022/7/3
 */
public class Solution {
    public static int way1(int[] arr) {
        int N = arr.length;
        if (arr[N - 1] != 0) {
            return process1(arr, N - 2, arr[N - 2], 2);
        } else {
            int ans = 0;
            for (int pre = 1; pre < 201; pre++) {
                ans += process1(arr, N - 2, pre, 2);
            }
            return ans;
        }
    }

    public static int process1(int[] arr, int i, int v, int s) {
        if (i == 0) {
            return (s == 0 || s == 1) && (arr[0] == 0 || arr[0] == v) ? 1 : 0;
        }
        if (arr[i] != 0 && arr[i] != v) {
            return 0;
        }
        int ans = 0;
        if (s == 0 || s == 1) {
            for (int pre = 1; pre < 201; pre++) {
                ans += process1(arr, i - 1, pre, pre < arr[i] ? 0 : (pre == arr[i] ? 1 : 2));
            }
        } else {
            for (int pre = v; pre < 201; pre++) {
                ans += process1(arr, i - 1, pre, pre == arr[i] ? 1 : 2);
            }
        }
        return ans;
    }

    public static int process2(int[] arr, int i, int v, int s) {
        if (i == 0) {
            return (s == 0 || s == 1) && (arr[i] == 0 || arr[i] == v) ? 1 : 0;
        }
        if (arr[i] != 0 && arr[i] != v) {
            return 0;
        }
        int ans = 0;
        if (s == 0 || s == 1) {
            for (int pre = 1; pre < v; pre++) {
                ans += process2(arr, i - 1, pre, 0);
            }
        }
        ans += process2(arr, i - 1, v, 1);
        for (int pre = v + 1; pre < 201; pre++) {
            ans += process2(arr, i - 1, pre, 2);
        }
        return ans;
    }

    public static int ways2(int[] arr) {
        int N = arr.length;
        int[][][] help = new int[N][201][3];
        if (arr[0] != 0) {
            help[0][arr[0]][0] = 1;
            help[0][arr[0]][1] = 1;
        } else {
            for (int v = 1; v < 201; v++) {
                help[0][v][0] = 1;
                help[0][v][1] = 1;
            }
        }
        for (int i = 0; i < N; i++) {
            for (int v = 0; v < 201; v++) {
                for (int s = 0; s < 3; s++) {
                    if (arr[i] == 0 || arr[i] == v) {
                        if (s == 0 || s == 1) {
                            for (int pre = 1; pre < v; pre++) {
                                help[i][pre][s] += help[i - 1][pre][0];
                            }
                        }
                        help[i][v][s] += help[i-1][v][1];
                        for (int pre = v + 1; pre < 201; pre++) {
                            help[i][v][s] += help[i - 1][pre][2];
                        }
                    }
                }
            }
        }
        if (arr[N - 1] != 0) {
            return help[N-2][arr[N-2]][2];
        } else {
            int ans = 0;
            for (int pre = 1; pre < 201; pre++) {
                ans += help[N-2][pre][2];
            }
            return ans;
        }
    }
}
